package com.caochenlei.sort;

import java.util.Arrays;

public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void radixSort(int[] arr) {
        //获取当前数组中的最大值的位数
        int maxElementLength = String.valueOf(Arrays.stream(arr).max().getAsInt()).length();
        //创建十个桶，每个桶是一维数组
        int[][] bucket = new int[10][arr.length];
        //十个索引指向对应桶内元素位置
        int[] bucketIndex = new int[10];
        //开始循环将各位数放入桶中排序
        for (int i = 0, n = 1; i < maxElementLength; i++, n *= 10) {
            for (int j = 0; j < arr.length; j++) {              //循环获取每一个元素值
                int digit = arr[j] / n % 10;                    //获取当前位数字（0-9）
                bucket[digit][bucketIndex[digit]] = arr[j];     //放入指定的桶内（0-9）
                bucketIndex[digit]++;                           //桶内的索引加加
            }
            int index = 0;                                      //用于指向原数组的索引，起始下标为零
            for (int k = 0; k < bucketIndex.length; k++) {      //依次获取桶内数据并重新填充到原数组
                if (bucketIndex[k] != 0) {                      //桶索引不等于零就说明这个桶内有数据
                    for (int l = 0; l < bucketIndex[k]; l++) {  //有数据就把这个桶内的数据一一拿出来
                        arr[index++] = bucket[k][l];            //拿出来以后就放到原数组中的指定位置
                    }
                }
                bucketIndex[k] = 0;                             //这个桶内数据拿完，需要让这个桶重置
            }
        }
    }
}
